МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра автоматизованих систем управління
/
Лабораторна робота №7-8
з дисципліни “Математичні методи дослідження операцій”
на тему
« Транспортна задача.
Метод потенціалів»
Львів – 2012
Мета роботи: набуття навиків розв’язку транспортної задачі лінійного програмування, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях в Еxcel, вивчення та оволодіння навиками розв’язання оптимізаційних задач в середовищі MathCad, набуття навиків розв’язку транспортної задачі за допомогою математичних пакетів та розробки оригінальної програми.
План
Короткі теоретичні відомості.
Постановка задачі
Знаходження базового рішення закритої транспортної задачі (ТЗ) шляхом північно-західного кута (ПЗК) і розв’язання транспортної задачі методом потенціалів.
Знаходження базового рішення закритої транспортної задачі (ТЗ) шляхом найменшої вартості (НВ) і розв’язання транспортної задачі методом потенціалів.
Знайти базове рішення відкритої транспортної задачі (ТЗ) шляхом найменшої вартості (НВ) і розв’язання транспортної задачі методом потенціалів.
Розв’язання за допомогою пакету програм MS Exel.
Розв’язання за допомогою пакету програм Optimal 1_4
Розв’язання за допомогою власної програми.
Хід роботи
1. Короткі теоретичні відомості
Постановка транспортної задачі
В m пунктах виробництва А1, А2, ... ,Аm в наявності запаси якогось однорідного продукту в кількостях а1, а2, ... ,аm одиниць. Необхідність отримання цього продукту в пунктах споживання B1, B2, ... ,Bn складає b1, b2, ... ,bn одиниць відповідно. З кожного пункту виробництва можливе транспортування продукту в будь-який пункт споживання. Транспортні витрати на перевезення одиниці продукції з п. Ai в Bj задані і складають cij, 1( i ( m, 1 ( j ( n.
Розв’язування задачі полягає в тому, щоб знайти такий план перевезень, при якому весь продукт буде вивезено з пунктів виробництва в пункти споживання з мінімальними сумарними транспортними затратами.
Умови Т-задачі записуються у вигляді
ai
С =
bj b1 b2 b3 … bn
Введемо змінні хij ( 0, 1( i ( m, 1 ( j ( n, що означають величину вантажу, який перевозиться з i-ого пункту виробництва ( ai ) в j пункт споживання ( bj ).
Необхідно знайти множину значень змінних хij ( 0, мінімізуючи функцію
L = ,
з виконанням умов
Матрицю
Х =
називають планом перевезень Т-задачі.
Визначення початкового опорного плану.
Метод «північно-західного кута» (ПЗК).
Визначаємо елементи матриці Х0 , починаючи з лівого верхнього кута. Знаходимо величину х11 = min{a1, b1}. Якщо b1 < a1, то х11 = b1, і перший стовбець «закритий» для розрахунку решти елементів, тобто хі1 = 0, і = 2, ..., m. Якщо b1 > a1, то х11 = a1, і перший рядок «закритий» для розрахунку решти елементів, тобто х1j = 0, j = 2, ..., n.
Припустимо, що вже виконано t кроків.
Тоді обчислення на t + 1 кроці проводиться за наступною схемою. Нехай ( + ( = t + 2. Знаходимо x(( = min{}, де
.
Якщо , то заповнюється (-ий рядок матриці, починаючи з ((+1)-го елемента, нулями. Якщо , то заповнюється нулями (-й стовбець, починаючи з ((+1)-ї строки. При цьому
;
Метод потенціалів розв’язування транспортної задачі.
Алгоритм методу потенціалів розв’язування Т-задачі складається з попереднього етапу і скінченного числа ітерацій.
Попередній етап.
1. Будується початковий опорний план Х0.
2. Обчислюється оціночна матриця
Δ1 = ,
де ui i vj – потенціали i-ого пункту виробництва та пункту споживання j, для яких виконується умова для хij ( 0 (базових клітин). Для зручності вибирається u1 = 0. Позиція в матриці Δ1, яка відпов...